﻿// 2-1 Quick Power (10分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。


#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
const int MOD = 10007;
/*int Power(int n, int k)
{
	int i = 0;
	int j = 0;
	if (n != 2) 
	{
		for (; k > 0; k=k >> 1 )
		{
			if (k & 1)
			{
				i = (i + n * (Power(2, j))) % MOD;
			}
			else
			{

			}
			j++;
		}
	}
	else
	{
		i = 2;
		for (; k > 0; k--)
		{
			i = i << 1;

		}
		i = i / 2;
	}
	return i;
};
int Power(int n, int k)
{
	n = n % MOD;
	if (k != 0) 
	{
		int i = 0;
		int j = 0;
		if (k & 1)
		{
			i = Power(n, (k - 1) >>1);
			//i = i % MOD;
			
			return ((i * i * n) % MOD +  MOD) % MOD;
		}

		else {
			i = Power(n, k >> 1);
			//i = i % MOD;
			return ((i * i) % MOD + MOD) % MOD;
		}
	}
	else
	{
		return 1;
	}

}*/

int  Power(int a, int b) 
{
	a %= MOD;
	int res = 1;
	for (; b > 0; b >>= 1) {
		if (b & 1) res = (res * a) % MOD;
		a = (a * a) % MOD;
		
	}
	return res;
}

int main()
{
	int N, k;
	cin >> N >> k;
	printf("%d\n", Power(N, k));
	cout << int(pow(N, k))<<endl ;
	cout<<((int(pow(N, k))) % MOD + MOD) % MOD;
	return 0;
}

